package nowcoder;

/**
 * @author wangxi created on 2021/5/9 22:58
 * @version v1.0
 *
 * 实现函数 int sqrt(int x).
 * 计算并返回x的平方根（向下取整）
 */
public class Mysqrt {

    public int sqrt (int x) {
        // write code here
        if (x <= 0) {
            return 0;
        }
        // left从1开始
        int left = 1;
        int right = x;
        while (left <= right) {
            int mid = left + (right - left)/2;
            int temp = x/mid;
            // ((mid * mid < x) && ((mid + 1) * (mid + 1) < x)) 即满足向下取整
            if (temp == mid || ((mid < x /mid) && (mid + 1 > x/(mid + 1)))) {
                return mid;
            } else if (temp > mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}
